package com.javaDemo.ti;

/**
 * 二进制运算工具类
 * 
 * @author csy
 * @date 2021/3/14 16:47
 * @description 实现不使用四则运算符号的加法和幂运算
 *              参考：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
 */
public class BinaryAddition {

    /**
     * 使用位运算实现加法
     * 实现原理：
     * 1. 异或运算（^）：计算不带进位的和（相同位为0，不同位为1）
     * 2. 与运算左移（& <<）：计算进位（两个1会产生进位）
     * 3. 循环处理进位，直到没有进位为止
     *
     * @param a 第一个加数
     * @param b 第二个加数
     * @return 两数之和
     */
    public static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // 计算进位
            a ^= b; // 计算无进位和
            b = carry; // 将进位结果赋给b，继续循环处理
        }
        return a;
    }

    /**
     * 快速幂算法实现幂运算
     * 实现原理：
     * 1. 将指数m转换为二进制，例如：m = 13 = (1101)₂
     * 2. n^13 = n^(8+4+1) = n^8 * n^4 * n^1
     * 3. 通过位运算和循环，依次计算所需的幂
     *
     * @param base     底数
     * @param exponent 指数
     * @return base的exponent次方
     */
    public static int power(int base, int exponent) {
        int result = 1;
        int currentBase = base;

        while (exponent != 0) {
            if ((exponent & 1) == 1) {
                result *= currentBase;
            }
            currentBase *= currentBase;
            exponent >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试加法运算
        int a = 5, b = 3;
        System.out.printf("%d + %d = %d%n", a, b, add(a, b));

        // 测试幂运算
        System.out.printf("%d的%d次方 = %d%n", a, b, power(a, b));

        // 演示位运算基础
        System.out.println("\n位运算示例：");
        System.out.println("12 & 0x1 = " + (12 & 0x1) + " (判断奇偶性)");
        System.out.println("11 & 0x1 = " + (11 & 0x1) + " (判断奇偶性)");
        System.out.println("-111 & 0x1 = " + (-111 & 0x1) + " (负数的奇偶性)");
        System.out.println("-222 & 0x1 = " + (-222 & 0x1) + " (负数的奇偶性)");
    }
}